package com.ztom.hard;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * 序列化二叉树
 * <p>
 * https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
 *
 * @author ZhangTao
 */
public class Code02Codec {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 先序
     */
    public class Codec1 {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return "";
            }
            StringBuilder builder = new StringBuilder();
            Deque<TreeNode> stack = new LinkedList<>();
            stack.offerLast(root);
            TreeNode node;
            while (!stack.isEmpty()) {
                node = stack.pollLast();
                if (node == null) {
                    builder.append("#,");
                    continue;
                }
                builder.append(node.val).append(",");
                stack.offerLast(node.right);
                stack.offerLast(node.left);
            }
            return builder.substring(0, builder.length() - 1);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            return deserialize(Arrays.stream(data.split(",")).collect(Collectors.toList()));
        }

        public TreeNode deserialize(List<String> data) {
            if (data == null || data.isEmpty()) {
                return null;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode root = genNode(data.remove(0));
            if (root != null) {
                stack.offerLast(root);
            }
            TreeNode node;
            while (!stack.isEmpty()) {
                node = stack.pollLast();
                node.left = genNode(data.remove(0));
                node.right = genNode(data.remove(0));
                if (node.right != null) {
                    stack.offerLast(node.right);
                }
                if (node.left != null) {
                    stack.offerLast(node.left);
                }
            }

            return root;
        }

        private TreeNode genNode(String data) {
            if (Objects.equals(data, "#")) {
                return null;
            }
            return new TreeNode(Integer.parseInt(data));
        }
    }

    /**
     * 层次
     */
    public class Codec2 {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return null;
            }
            StringBuilder builder = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode node;
            while (!queue.isEmpty()) {
                node = queue.poll();
                if (node == null) {
                    builder.append("#,");
                    continue;
                }
                builder.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
            return builder.substring(0, builder.length() - 1);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            return deserialize(Arrays.stream(data.split(",")).collect(Collectors.toList()));
        }

        public TreeNode deserialize(List<String> data) {
            if (data == null || data.isEmpty()) {
                return null;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = genNode(data.remove(0));
            if (root != null) {
                queue.offer(root);
            }
            TreeNode node;
            while (!queue.isEmpty()) {
                node = queue.poll();
                node.left = genNode(data.remove(0));
                node.right = genNode(data.remove(0));
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            return root;
        }

        private TreeNode genNode(String data) {
            if (data == null || Objects.equals(data, "#")) {
                return null;
            }
            return new TreeNode(Integer.parseInt(data));
        }
    }

    /**
     *
     */
    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return null;
            }
            StringBuilder builder = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode node;
            while (!queue.isEmpty()) {
                node = queue.poll();
                if (node == null) {
                    builder.append("#,");
                    continue;
                }
                builder.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
            return builder.substring(0, builder.length() - 1);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }

            Queue<String> list = new LinkedList<>(Arrays.asList(data.split(",")));
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = genNode(list.poll());
            if (root != null) {
                queue.offer(root);
            }
            TreeNode node;
            while (!queue.isEmpty()) {
                node = queue.poll();
                node.left = genNode(list.poll());
                node.right = genNode(list.poll());
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            return root;
        }

        private TreeNode genNode(String data) {
            if (data == null || Objects.equals(data, "#")) {
                return null;
            }
            return new TreeNode(Integer.parseInt(data));
        }
    }
}
